package com.gxc.linkedList;

/**
 * 给你两个单链表的头节点 headA 和 headB ，
 * 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null
 */
public class IsLinkedListCross {

    /**
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode handle(ListNode headA, ListNode headB) {
        if (headA==null || headB ==null) return null;
        //判断链表是否存在环
        ListNode loopA = isLoop(headA);
        ListNode loopB = isLoop(headB);


        if (loopA!=null && loopB!=null) {
            /**
             * 两个链表都是环
             * 1.相交点不在环上，在入环前
             * 2.相交点在环上，如果相交点在环上，必定是入环的节点
             * 3.不想交
             */
            if (loopA == loopB) {
                //入环点相等。则相交点可能在入环前，把环移除，则转变成非环链表的相交点
                int lA = 0;
                ListNode node = headA;
                while (node != loopA) {
                    lA++;
                    node = node.next;
                }

                int lB = 0;
                node = headB;
                while (node != loopB) {
                    lB++;
                    node = node.next;
                }

                ListNode longer = null;
                ListNode shorter = null;
                int gap = 0;
                if (lA>=lB) {
                    gap = lA- lB;
                    longer = headA;
                    shorter = headB;
                } else {
                    gap = lB - lA;
                    longer = headB;
                    shorter = headA;
                }
                //更长的先走 两个链表的相差值
                while (gap > 0) {
                    longer = longer.next;
                    gap--;
                }
                //如果长度相等的两个链表相交，则会同时移动到同一个节点
                while (shorter != null) {
                    if (shorter == longer) return shorter;
                    shorter = shorter.next;
                    longer = longer.next;
                }
            } else {
                //判断两个环是否相交，如果相交，则另一个的入环点必定是该环的其中一个点
                ListNode node = loopB.next;
                while (node != loopB) {
                    if (node == loopA) return loopA;
                    node = node.next;
                }
                return null;
            }
        } else if(loopA!=null || loopB!=null) {
            //一个链表是环，一个不是环，则相交点必定不相交，如果相交。则两个链表必定都为环
            return null;
        } else {
            //链表都不是环，如果相交，则相加节点开始的到最后的节点一定是同一个
            //统计两个链表的长度
            int lA = 0;
            ListNode node = headA;
            while (node != null) {
                lA++;
                node = node.next;
            }

            int lB = 0;
            node = headB;
            while (node != null) {
                lB++;
                node = node.next;
            }

            ListNode longer = null;
            ListNode shorter = null;
            int gap = 0;
            if (lA>=lB) {
                gap = lA- lB;
                longer = headA;
                shorter = headB;
            } else {
                gap = lB - lA;
                longer = headB;
                shorter = headA;
            }
            //更长的先走 两个链表的相差值
            while (gap > 0) {
                longer = longer.next;
                gap--;
            }
            //如果长度相等的两个链表相交，则会同时移动到同一个节点
            while (shorter != null) {
                if (shorter == longer) return shorter;
                shorter = shorter.next;
                longer = longer.next;
            }
        }
        return null;
    }

    /**
     * 判断链表是否有环,如果有环，则返回入环点
     * 1.快慢指针判断是否有环，快指针能追上慢指针，则肯定有环
     * 2.如果快指针追上慢指针，则快指针返回头节点，步进改为1，当两个指针再次相遇每，则相遇的点必定为入环点
     * 证明
     *  假设环的长度为 l ,慢指针步进1，开指针步进2，当持续了n次后，快慢指针相遇，入环点步数k，环内步数l-k
     *  此时
     *      慢指针步数  n
     *      快指针步数  2n
     *      慢指针在环内走的步数  n-k
     *      快指针的总部  l + n-k = 2n  简化  l - k = n   简化  k = l - n
     *      则慢指针走继续走k不，快指针继续走k不，都刚好到达入环点，此时相交
     * @param head
     * @return
     */
    public ListNode isLoop(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast!=null) {
            if (fast == slow) {
                fast = head;
                while (fast!=null) {
                    fast = fast.next;
                    slow = slow.next;
                    //入环点
                    if (fast == slow) {
                        return fast;
                    }
                }
            }
            slow = slow.next;
            fast = fast.next != null ?fast.next.next:null;
        }
        return null;
    }

    public static class ListNode {
        int val;
        IsLinkedListCross.ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, IsLinkedListCross.ListNode next) { this.val = val; this.next = next; }
    }
}
